// 两数之和
// 输入：一个整数数组和一个目标整数
// 计算过程：在数组中找出和为目标值的两个整数
//  注意：不能为同一个元素
// 输出：两个数对应数组下组成的数组，如果不存在则返回空数组
// arr = [2,3,5,7,11,15], target = 10

/**
 * 方法1：暴力破解法
 *  使用一层循环，每次循环计算差值
 *  通过indexOf()方法判断，差值是否在数组中，
 *  如果存在，则返回两个值的索引
 *  如果不存在，则返回[]
 * 时间复杂度: o(n^2)
 */
function twoSum(array, target) {
    for (let index = 0; index < array.length; index++){
        let diff = target - array[index];
        let diffIndex = array.indexOf(diff);
        if (diffIndex !== -1 && diffIndex !== index) {
            return [diffIndex, index];
        }
    }
    return [];
}
const arr = [2,9,7,0,5,3,4,1];
const target = 10;//[7,1]这个是通过指向下标的位置指向了对应的数字
const target2 = 19;
const res1 = twoSum(arr, target);
const res2 = twoSum(arr, target2);
console.log('res1: ', res1);
console.log('res2: ', res2);

/**
 * 方法2：HashMap存储
 *  增加一个Map记录已经遍历过的数字及其索引值
 *  当遍历到一个新数字时，先计算出和目标值的差值，
 *  然后查询出差值是否在Map中出现过
 *  如果出现过，则之间拿出差值对应的索引值和当前数字对应的索引位
 *  如果遍历完成都没有出现过，则致敬返回[]
 * 时间复杂度: o(n)
 * 空间复杂度: o(n)
 */
function twoSum2(array,target) {
    const map = new Map();
    for (let index = 0; index<array.length;index++){
        const diff = target - array[index];
        if(!map.has(diff)){
            map.set(array[index], index);
        }else{
            return [map.get(diff), index];
        }
    }
    return [];
}
const arr2 = [3,9,22,55,10,93,20];
const target3 = 10;
const target4 = 19;
const res3 = twoSum2(arr2, target3);
const res4 = twoSum2(arr2, target4);
console.log('res3: ', res3);
console.log('res4: ', res4);